"""
quicksort_v1
实验指导书上的快排算法
"""
import random
import sys
sys.setrecursionlimit(1000)  # 将默认的递归深度修改为1100000


def rand_partition_v1(sequence, p, r):
    i = random.randint(p, r)
    sequence[r], sequence[i] = sequence[i], sequence[r]
    x = sequence[r]
    i = p
    for j in range(p, r):
        if sequence[j] <= x:
            sequence[i], sequence[j] = sequence[j], sequence[i]
            i += 1
    sequence[i], sequence[r] = sequence[r], sequence[i]
    return i


def _quicksort_v1(sequence, p, r):
    if p < r:
        q = rand_partition_v1(sequence, p, r)
        _quicksort_v1(sequence, p, q - 1)
        _quicksort_v1(sequence, q + 1, r)


def quicksort_v1(sequence):
    _quicksort_v1(sequence, 0, len(sequence) - 1)
